package org.algorithm.biubiu.wheel_1.回溯算法;

import org.junit.Test;

import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.Stream;

/**
 * 给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
 * 47. 全排列 II
 * 链接：https://leetcode-cn.com/problems/permutations-ii/
 */
public class $4月23日$全排列2 {



    @Test
    public  void test(){
        int[] arr={1,2,3};
        permuteUnique(arr);
    }

    List<List<Integer>> res =new ArrayList();
    int[] arr;
    public List<List<Integer>> permuteUnique(int[] nums) {

        this.arr = nums;
        Arrays.sort(nums);
        backTrack(0);
        return res;
    }

    List<Integer> cur = new ArrayList();

    public void backTrack(int step){

        if(step==arr.length){
            res.add(toList(arr));
            return ;
        }
        Set<Integer> set = new HashSet();

        for(int i=step;i<arr.length;i++){
            if(set.contains(arr[i])) continue;
            set.add(arr[i]);

            swap(step,i);
            backTrack(step+1);
            swap(i,step);
        }
    }


    public void swap(int step,int i){
        if(step==i) return ;
        System.out.println(step +"---->" + i);
        int tmp;
        tmp = arr[step];
        arr[step] = arr[i];
        arr[i] = tmp;
    }

    public List toList(int[] arr){
        List res = new ArrayList();
        for(int e: arr){
            res.add(e);
        }
        return res;

    }
}
